﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using TangoGames.Primitives3D;

namespace TangoGames.Scene
{

    public class PathMap:IPathMap
    {

        #region Fields

        /// <summary>
        /// tabuleiro
        /// </summary>
        private Rectangle board;

        /// <summary>
        /// Tamanho da casa
        /// </summary>
        private Point squareSize;

        /// <summary>
        /// Tamanho do mapa em números de quadrados
        /// </summary>
        private Point dimensions =  new Point();

        /// <summary>
        /// Array Mapa
        /// </summary>
        private int[,] arrayMap;

        /// <summary>
        /// Calcula usando passo diagonal
        /// </summary>
        bool diagonalStep = true;

        /// <summary>
        /// Calcula caminho realistico
        /// </summary>
        bool realisticWay = true;

        /// <summary>
        /// Cubo de desenho teste
        /// </summary>
        CubePrimitive cube;

        #endregion

        #region Properties

        /// <summary>
        /// Limites do tabuleiro
        /// </summary>
        public Rectangle Boardbounds { get { return board; } set  { board=value;} }

        /// <summary>
        /// Tamanho de casa do tabuleiro
        /// </summary>
        public Point SquareSize { get { return squareSize; } set { squareSize = value; } }

        /// <summary>
        /// Dimensões do tabuleiro em quantidade de casa N x M
        /// </summary>
        public Point Dimensions { get { return dimensions; } set { dimensions = value; } }

        /// <summary>
        /// Array de configuração do Mapa
        /// </summary>
        public int[,] ArrayMap { get { return arrayMap; } set { arrayMap = value; } }

        /// <summary>
        /// Calcula caminho usando passo diagonal
        /// </summary>
        public bool DiagonalStep { get { return diagonalStep; } set { diagonalStep = value; } }

        /// <summary>
        /// Calcula caminho realistico
        /// </summary>
        public bool RealisticWay { get { return realisticWay;} set { realisticWay = value;} }

        #endregion

        #region Methods

        /// <summary>
        /// 
        /// </summary>
        /// <param name="board"></param>
        /// <param name="SquareSize"></param>
        public PathMap(Rectangle board,Point squareSize)
        { 
            this.board=board;
            this.squareSize = squareSize;
            this.arrayMap = BuidArrayMap(board, squareSize, out dimensions);
        }

        /// <summary>
        /// Cria o array vazio
        /// </summary>
        /// <param name="board"></param>
        /// <param name="squareSize"></param>
        /// <param name="dimensions"></param>
        /// <returns></returns>
        public static int[,] BuidArrayMap(Rectangle board, Point squareSize, out Point dimensions)
        {
            dimensions = new Point();
            dimensions.X = (board.Width / squareSize.X);
            dimensions.Y = (board.Height / squareSize.Y);
            int[,] arrayMap = new int[dimensions.X, dimensions.Y];
            for (int x = 0 ; x < dimensions.X; x++)
                for (int y = 0; y < dimensions.Y; y++)
                { 
                    arrayMap[x,y]=0;
                }
            return arrayMap;
        }

        /// <summary>
        /// Marca area ocupada
        /// </summary>
        /// <param name="box"></param>
        public void FlagAsBusy(BoundingBox box) 
        {
            Vector2 ini = new Vector2 ( box.Min.X, box.Min.Z);
            Vector2 end = new Vector2 ( box.Max.X, box.Max.Z);
            FlagAsBusy(ini,end);
        }
        public void FlagAsBusy(Rectangle ret)
        {
            Vector2 ini = new Vector2(ret.Left , ret.Top );
            Vector2 end = new Vector2(ret.Right, ret.Bottom);
            FlagAsBusy(ini, end);
        }
        /// <summary>
        /// Marca área ocupada
        /// </summary>
        /// <param name="PointIni"></param>
        /// <param name="PontEnd"></param>
        public void FlagAsBusy(Vector2 PointIni, Vector2 PontEnd)
        {
            Point ini = ReversePoint(PointIni);
            Point end = ReversePoint(PontEnd);

            for (int x = ini.X; x <= end.X; x++)
            {
                for (int y = ini.Y ; y <= end.Y; y++)
                {
                    arrayMap[x, y]++;
                }
            }

        }

        /// <summary>
        /// Marca área desocupada
        /// </summary>
        /// <param name="box"></param>
        public void FlagAsFree(BoundingBox box)
        {
            Vector2 ini = new Vector2(box.Min.X, box.Min.Z);
            Vector2 end = new Vector2(box.Max.X, box.Max.Z);
            FlagAsFree(ini, end);
        }

        public void FlagAsFree(Rectangle ret)
        {
            Vector2 ini = new Vector2(ret.Left, ret.Top);
            Vector2 end = new Vector2(ret.Right, ret.Bottom);
            FlagAsFree(ini, end);
        }

        /// <summary>
        /// Marca área desocupada
        /// </summary>
        public void FlagAsFree(Vector2 PointIni, Vector2 PontEnd)
        {
            Point ini = ReversePoint(PointIni);
            Point end = ReversePoint(PontEnd);

            for (int x = ini.X; x <= end.X; x++)
            {
                for (int y = ini.Y; y <= end.Y; y++)
                {
                    arrayMap[x, y]--;
                }
            }
        }

        /// <summary>
        /// Converte ponto real uma referencia de quadrante quadrante
        /// </summary>
        /// <param name="point"></param>
        /// <returns></returns>
        public Point ReversePoint(Vector2 point)
        {
            float X = (point.X - board.Left) / squareSize.X;

            float Y = (point.Y - board.Top) / squareSize.Y;

            return new Point((int)Math.Floor((decimal)X), (int)Math.Floor((decimal)Y));

        }

        /// <summary>
        /// Converte uma referencia de quadrante quadrante em ponto real
        /// </summary>
        /// <param name="point"></param>
        /// <returns></returns>
        public Vector2 ConvertPoint(Point point)
        {
            Vector2 p = new Vector2();

            p.X = (point.X * squareSize.X) + board.Left + ( squareSize.X  / 2);

            p.Y = (point.Y * squareSize.Y) + board.Top + (squareSize.Y / 2);

            return p;

        }

        #endregion

        #region Path Calculation

        /// <summary>
        /// Encontra o melhor caminho
        /// </summary>
        /// <param name="source"></param>
        /// <param name="destination"></param>
        /// <returns></returns>
        public List<Point> FindPath(Point source, Point destination, bool wayPoints)
        {
            List<Point> points = new List<Point>();

            //inicializa array temporário
            int[,] tmpArrayMap = new int[dimensions.X, dimensions.Y];
            for (int x = 0 ; x < dimensions.X; x++)
                for (int y = 0; y < dimensions.Y; y++)
                { 
                    tmpArrayMap[x,y]=0;
                }


            tmpArrayMap[source.X, source.Y] = 1;
            tmpArrayMap[destination.X,destination.Y] = -1;

            points.Add(source);

            int iteractions = iterate(points, ref tmpArrayMap);

            List<Point> path = new List<Point>();

            path = GetPathArray(destination, iteractions, path, ref tmpArrayMap);

            if (wayPoints) path = GetWayPoints(path);

            return path;

        }

        /// <summary>
        /// Retorna o melhor caminho para o destino
        /// </summary>
        /// <param name="destination"></param>
        /// <param name="iteractions"></param>
        /// <param name="path"></param>
        /// <param name="tmpArrayMap"></param>
        /// <returns></returns>
        private List<Point> GetPathArray(Point destination, int iteractions, List<Point> path, ref int[,] tmpArrayMap)
        {
            if (iteractions == 0)
            {
                path.Reverse();
                return path;
            }
            Point stepPoint = choosesBestStep(destination, iteractions, path, ref tmpArrayMap);
            if (stepPoint.X == -1) return path;
            path.Add(stepPoint);
            return GetPathArray(stepPoint, iteractions -1 , path, ref tmpArrayMap) ;
        }

        /// <summary>
        /// Calcula o peso do pontos pelo perimetro
        /// </summary>
        /// <param name="point"></param>
        /// <param name="stepCount"></param>
        /// <param name="tmpArrayMap"></param>
        /// <returns></returns>
        private int PerimeterValidPointsValue(Point point, ref int[,] tmpArrayMap, int dist=1)
        {
            if (!realisticWay) return 1;
            int x, y, v;
            List<Point> best = new List<Point>();
            int min = tmpArrayMap[point.X, point.Y];
            int max = dimensions.X * dimensions.Y;

            if (dist > max) return max;

            if (min < 1) min = max;

            for (int dx = -1; dx < 2; dx++)
            {
                x = point.X + dx;
                if (x < 0 || x > (dimensions.X - 1)) continue;
                for (int dy = -1; dy < 2; dy++)
                {
                    y = point.Y + dy;
                    if (dx == 0 && dy == 0) continue;
                    if (y < 0 || y > (dimensions.Y - 1)) continue;
                    v = tmpArrayMap[x, y];
                    if (arrayMap[x, y] > 0 && v!=1) continue;
                    if (v < 1) continue;
                    if ( v <= min )
                    {
                        if (v < min) best.Clear();
                        best.Add(new Point(x, y));
                        min = v; 
                    }
                }
            }
            
            if ( min == 1 ) return dist;

            if (best.Count == 0)  return max;

            int calcdist = 0;
            int mindist = max;

            for (int k = 0; k < best.Count; k++)
            { 
                calcdist = PerimeterValidPointsValue(best[k],ref tmpArrayMap,dist+1);
                if (calcdist < mindist) mindist = calcdist;
            }


            return mindist;

        }

        /// <summary>
        /// Escolhe o melhor ponto pelo peso do perímetro
        /// </summary>
        /// <param name="point"></param>
        /// <param name="iteractions"></param>
        /// <param name="path"></param>
        /// <param name="tmpArrayMap"></param>
        /// <returns></returns>
        private Point choosesBestStep(Point point, int iteractions, List<Point> path, ref int[,] tmpArrayMap )
        {

            List<Point> points = new List<Point>();
            List<Point> diagpoints = new List<Point>();

            int x, y, v;
            for (int dx = -1; dx < 2; dx++)
            {
                x = point.X + dx;
                if (x < 0 || x > (dimensions.X - 1)) continue;
                for (int dy = -1; dy < 2; dy++)
                {
                    y = point.Y + dy;
                    if (dx == 0 && dy == 0) continue;
                    if (y < 0 || y > (dimensions.Y - 1)) continue;
                    v = tmpArrayMap[x, y];
                    if (arrayMap[x, y] > 0 && v!=1 ) continue;
                    if (v != iteractions) continue;
                    if ((dx != 0) && (dy != 0)) diagpoints.Add(new Point(x, y));
                    else points.Add(new Point(x, y));
                }
            }

            Point best = new Point(-1,-1);
            float minValue = dimensions.X * dimensions.Y;
            float value;

            if (diagonalStep)
            {
                for (int k = 0; k < diagpoints.Count; k++)
                {
                    value = PerimeterValidPointsValue(diagpoints[k], ref tmpArrayMap);
                    if (value <= minValue)
                    {
                        best = diagpoints[k];
                        minValue = value;
                    }
                }
            }

            for (int k = 0; k < points.Count; k++)
            {
                value = PerimeterValidPointsValue(points[k], ref tmpArrayMap);
                if (value <= minValue)
                {
                    best = points[k];
                    minValue = value;
                }
            }

            return best;
        }

        ///// <summary>
        ///// Retorna o melhor caminho para o destino
        ///// </summary>
        ///// <param name="destination"></param>
        ///// <param name="iteractions"></param>
        ///// <param name="path"></param>
        ///// <param name="tmpArrayMap"></param>
        ///// <returns></returns>
        //private List<Point> GetPathArrayOld(Point destination, int iteractions, List<Point> path, ref int[,] tmpArrayMap, bool zigzag)
        //{
        //    int i = destination.X;
        //    int j = destination.Y;

        //    int[] vlx;
        //    int[] vly;

        //    if (iteractions == 0)
        //    {
        //        path.Reverse();
        //        return path;
        //    }

        //    //if (realisticWay)
        //    //{
        //    //    if (zigzag)
        //    //    {
        //    //       vly = new int[] { 0 };
        //    //       vlx = new int[] { 1, -1 };

        //    //    }
        //    //    else 
        //    //    {
        //    //        vlx = new int[] { 0 };
        //    //        vly = new int[] { 1, -1 };
        //    //    }
        //    //    foreach (int vx in vlx)
        //    //    {
        //    //        foreach (int vy in vly)
        //    //        {
        //    //            if (DiscoveredPath(i, j, vx, vy, iteractions, ref tmpArrayMap, ref path)) return GetPathArray(new Point(i + vx, j + vy), iteractions - 1, path, ref tmpArrayMap,!zigzag);
        //    //        }
        //    //    }
        //    //}


        //    vlx = new int[] { -1, 0, 1 };
        //    vly = new int[] { 1, 0, -1 };

        //    //Verifica todas posições entorno do ponto
        //    foreach (int vx in vlx)
        //    {
        //        foreach (int vy in vly)
        //        {
        //            if (DiscoveredPath(i, j, vx, vy, iteractions, ref tmpArrayMap, ref path)) return GetPathArrayOld(new Point(i + vx, j + vy), iteractions - 1, path, ref tmpArrayMap, !zigzag);
        //        }
        //    }

        //    return new List<Point>();
        //}


        ///// <summary>
        ///// Descobre se o ponto é um parte de um caminho mínimo
        ///// </summary>
        ///// <param name="x"></param>
        ///// <param name="y"></param>
        ///// <param name="lookX"></param>
        ///// <param name="looKY"></param>
        ///// <param name="iter"></param>
        ///// <param name="tmp"></param>
        ///// <param name="path"></param>
        ///// <returns></returns>
        //private bool DiscoveredPath(int x, int y, int lookX, int looKY, int iter, ref int[,] tmp, ref List<Point> path)
        //{
        //    if (lookX == 0 && looKY == 0) return false;
        //    if (!diagonalStep)
        //    {
        //        if (!(lookX == 0 || looKY == 0)) return false;
        //    }
        //    int i = x + lookX;
        //    int j = y + looKY;
        //    if (i < 0 || i > (dimensions.X - 1)) return false;
        //    if (j < 0 || j > (dimensions.Y - 1)) return false;
        //    if (tmp[i, j] != iter) return false;
        //    path.Add(new Point(i, j));
        //    return true;
        //}

        /// <summary>
        /// Iteração pelo mapa buscando o melhor caminho
        /// </summary>
        /// <param name="points"></param>
        /// <param name="tmpArrayMap"></param>
        /// <returns></returns>
        private int iterate(List<Point> points, ref int[,] tmpArrayMap, int iteration = 1)
        {
            List<Point> newPoints = new List<Point>();

            for (int key = 0; key < points.Count; key++)
            {
                int i = points[key].X;
                int j = points[key].Y;

                // verifica se chegou ao fim
                if ( AddPoint( i, j, -1,  0, iteration, ref tmpArrayMap,ref newPoints ) ) return iteration;
                if ( AddPoint( i, j,  0, -1, iteration, ref tmpArrayMap,ref newPoints ) ) return iteration;
                if ( AddPoint( i, j,  1,  0, iteration, ref tmpArrayMap,ref newPoints ) ) return iteration;
                if ( AddPoint( i, j,  0,  1, iteration, ref tmpArrayMap,ref newPoints ) ) return iteration;

                // verifica se chegou ao fim com diagonal
                if (diagonalStep)
                {
                    if (AddPoint(i, j, -1, -1, iteration, ref tmpArrayMap, ref newPoints)) return iteration;
                    if (AddPoint(i, j,  1,  1, iteration, ref tmpArrayMap, ref newPoints)) return iteration;
                    if (AddPoint(i, j, -1,  1, iteration, ref tmpArrayMap, ref newPoints)) return iteration;
                    if (AddPoint(i, j,  1, -1, iteration, ref tmpArrayMap, ref newPoints)) return iteration;
                }

            }

            //Finaliza iteracoes
            if ( newPoints.Count == 0 || iteration > (dimensions.X * dimensions.Y) ) return iteration;

            //processa pontos novos
            return iterate(newPoints, ref tmpArrayMap, iteration + 1);
        }

        /// <summary>
        /// Verifica o ponto se chegou no destino ou adiciona ponto novo
        /// </summary>
        /// <param name="i"></param>
        /// <param name="j"></param>
        /// <param name="dx"></param>
        /// <param name="dy"></param>
        /// <param name="iteration"></param>
        /// <param name="tmpArrayMap"></param>
        /// <param name="newPoints"></param>
        /// <returns></returns>
        private bool AddPoint(int i, int j, int dx, int dy, int iteration, ref int[,] tmpArrayMap, ref List<Point> newPoints)
        {
            int x = i + dx;
            int y = j + dy;

            //passou dos limites do mapa
            if (x < 0 || x > (dimensions.X - 1)) return false;
            if (y < 0 || y > (dimensions.Y - 1)) return false;

            int v = tmpArrayMap[x, y];

            //chegou no destino (fim)
            if (i > 0 &&  v == -1) return true;

            if ( v == 0 && arrayMap[x, y] <= 0)
            {
                    tmpArrayMap[x, y] = iteration + 1;
                    newPoints.Add(new Point(x, y));
            }

            return false;

        }

        /// <summary>
        /// Cria caminho mais curto
        /// </summary>
        /// <param name="path"></param>
        /// <returns></returns>
        public List<Point> GetWayPoints(List<Point> path)
        {
            Dictionary<int, Point> shortPath = new Dictionary<int, Point>();
            int shortIter = 0;
            int diffX = 0;
            int diffY = 0;
            for (int i = 0; i < path.Count; i++)
            {
                if (i > 0) 
                {
                    if (!(diffX == 0 && diffY == 0) && diffX == path[i].X - path[i - 1].X && diffY == path[i].Y - path[i - 1].Y) shortIter--;
                    diffX = path[i].X - path[i-1].X;
                    diffY = path[i].Y - path[i-1].Y;
                }
                shortPath[shortIter] = path[i];
                shortIter++;
            }

            List<Point> shortPathResult = new List<Point>();

            for (int i = 0; i < shortPath.Count; i++)
            {
                shortPathResult.Add(shortPath[i]);
            }
            return shortPathResult;
        }

        #endregion

        #region Debug Utilities
        /// <summary>
        /// Gera quadrados de depuração
        /// </summary>
        /// <param name="game"></param>
        /// <param name="camera"></param>
        /// <param name="path"></param>
        public void DrawDebugSquares(Game game, ICamera camera, List<Point> path)
        {
            Color cor;

            int[,] pathArray = new int[dimensions.X, dimensions.Y];
            for (int x = 0; x < dimensions.X; x++)
            {
                for (int y = 0; y < dimensions.Y; y++)
                {   
                    pathArray[x, y] = 0;

                }
            }

            if (path != null)
            {

                foreach (Point p in path)
                {
                    pathArray[p.X, p.Y] = 1;
                }
            }
            Matrix world;
            if (cube == null)
                cube = new CubePrimitive(game.GraphicsDevice, squareSize.X - 0.5f, 1, squareSize.Y - 0.5f);

            for (int x = 0; x < dimensions.X; x++)
            {
                for (int y = 0; y < dimensions.Y; y++)
                {
                    world = Matrix.CreateTranslation((board.Left + squareSize.X * x) + (squareSize.X / 2), 0, (board.Top + squareSize.Y * y) + (squareSize.Y / 2));

                    if (arrayMap[x, y] > 0)
                    { cor = Color.Red; }
                    else if (pathArray[x, y] == 1)
                    { cor = Color.Yellow; }
                    else
                    { cor = Color.Green; }
                    cor.A = 125;
                    cube.Draw(world, camera.ViewMatrix, camera.ProjectionMatrix, cor);
                }
            }
        }

        /// <summary>
        /// Desenha quadrados para testes
        /// </summary>
        /// <param name="effect"></param>
        public void DrawDebugSquares(Game game, ICamera camera)
        {
            List<Point> path = new List<Point>();
            DrawDebugSquares(game, camera, path);
        }

        #endregion

    }
}

